<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /* 
      思路：因为路径和=左子树的最大路径和+右子树的最大路径和+root.val
      因此，我们需要知道左右子树的最大路径和，这就跟二叉树的最近公共祖先一样，我们需要从下往上遍历
      因此，用后序遍历
      
      */
            var maxPathSum = function (root) {
                let maxSum = root.val
                function postOrder(root) {
                    if (!root) return 0
                    let leftSum = postOrder(root.left)
                    let rightSum = postOrder(root.right)
                    maxSum = Math.max(maxSum, root.val + leftSum + rightSum)
                    let returnMaxSum = Math.max(0, leftSum, rightSum) + root.val
                    return returnMaxSum > 0 ? returnMaxSum : 0
                }
                postOrder(root)
                return maxSum
            }
        </script>
    </body>
</html>
